Traditionally, computing environments in which computer programs are run have been single threaded. A “thread,” as used herein, is part of a program that can execute independently of other parts of the program. Accordingly, a single threaded environment requires that only one thread of a program may be executed at a time. This places constraints on both users and programs because users are only able to run one program at a time and that program is only able to execute a single thread at a time.
To overcome the deficiencies associated with single threaded environments, computing environments have been created that are multi-threaded. “Multi-threaded,” as used herein, is the ability of an operating system to execute different parts of a program, or programs, called threads, simultaneously. Accordingly, a program is typically able to run multiple threads concurrently. For example, a spreadsheet program may calculate a complex formula taking minutes to complete while at the same time permitting the user to continue editing the spreadsheet. Additionally, a user may be able to run threads from different applications at the same time.
However, a problem arises when two or more threads of the same or different programs attempt to access the same “data object.” A “data object” as used herein may be any type of data stored on a computing device. For example, a data object may be a file, such as an image file, data file, database file, a software component, or any other type of computing information. Concurrent access of the same data object may result in corruption of a program's data structures, ultimately causing the computer to fail. Therefore, techniques have been created in an effort to manage access to data objects in a multi-threaded environment by locking the data object once accessed. However, such techniques have resulted in inefficient management of threads.
In general, thread requests in a multi-threaded environment fall into two categories, non-contended and contended. Non-contended cases occur when: (1) an exclusive acquire thread attempts to access a data object that is currently in a free state, i.e., unlocked; (2) a shared acquire thread attempts to access a data object that is not exclusively locked (i.e., being accessed by an exclusive acquire thread); (3) an exclusive release thread that attempts to release an exclusively acquired data object that has not met contention; and (4) a shared release thread that attempts to release a data object that is shared by one or more shared acquire threads and that has not met contention.
Contended cases result in two circumstances. First, when an exclusive acquire thread attempts to exclusively acquire a data object that is currently locked by another exclusive acquire thread or by a shared acquire thread. An exclusive acquire thread will always result in a contended case when a data object is locked by either a previous exclusive acquire thread or by one or more shared acquire threads. Second, a contended case also results when a shared acquire thread attempts to access a data object that is locked by an exclusive acquire thread.
FIG. 1 illustrates a block diagram of a typical lock that is used to manage access to a data object in a multi-threaded environment. In particular, a typical lock 101 includes three control bits, a shared owners count control bit 103, an exclusive control bit 105, and a waiters control bit 107. If there are no threads attempting to access the data object being managed by lock 101, each of the control bits 103-107 are low, or in a zero state, thereby indicating that the data object managed by the lock 101 is currently available.
With continued reference to FIG. 1, in a first example, exclusive acquire thread 121 attempts to acquire a data object (not shown) that is controlled by a lock 101 when that data object is in a free state. The lock 101 identifies that the data object is in a free state because the shared owner count 103 is in a zero or low state, the exclusive control bit 105 is in a zero or low state, and the waiters control bit 107 is in a zero or low state. In response to receiving an exclusive acquire thread 121, the lock 101 transitions to a lock 111 and includes a shared owner count of a low or zero state 113, an exclusive control bit 115 having a high or 1 state, and a waiters control bit 117 having a zero or low state. Transitioning the exclusive control bit 115 to a high state identifies the data object as being exclusively locked.
Another example of a non-contended case results from a shared acquire thread 131 attempting to access a data object that is currently not locked by an exclusive acquire. In such a case, the data object being accessed may have multiple shared acquire threads accessing the data object thereby resulting in a shared owners count 103 of any number illustrating the number of shared acquire threads currently accessing the data object. For example, if there were three shared acquire threads accessing the data object, the shared owners count 103 would have a value of 3. Because the object is not exclusively acquired, the exclusive control bit 105 is in a low state and the waiters control bit 107 is also in a low state. In response to receiving a shared acquire thread 131, the lock 101 transitions to the lock 111. The state of the lock 111 in response to a shared acquire thread 131 results in a shared owners count 113 being incremented by 1 from whatever the value of the shared owners count 103 contained in the lock 101. For example, if the shared owners count 103 had a value of 3, access by a shared acquire thread 131 would result in a shared owners count of 4. Likewise, because the acquire thread is a shared acquire and there is no contention, the exclusive control bit 115 remains low and the waiters control bit 117 also remains low.
Another non-contended case results from receipt of an exclusive release thread 141, to release a data object that is currently locked by an exclusive acquire thread. A data object is identified as being exclusively locked by the lock control bit 105 being high, the shared owners count control bit 103 being low and the waiters control bit 107 also being low. Receiving the exclusive release 141 results in a transition to lock 111 with a shared owners count 113 remaining low, an exclusive control bit 115 transitioning to a low state and the waiters control bit 117 remaining in a low state. The transition of the exclusive control bit 105 from a high state to an exclusive control bit 115 having a low state indicates that the data object controlled by the lock 101 is no longer locked (i.e., being accessed) by an exclusive acquire thread.
A shared release thread 151 releasing a data object that is not exclusively locked, identified by the exclusive control bit 105 being low, also results in a non-contended case. A data object controlled by a shared lock may be shared by multiple shared acquire threads, as illustrated by shared owners count 103 being any number (N) identifying the number of shared acquires currently accessing the data object. In response to receiving a shared release 151, the lock 101 transitions to the lock 111 and the shared owners count 113 is decremented by 1, illustrating the release of one shared acquire thread. The shared owners count 113 is decremented by 1 for all shared releases where the shared owners count is greater than or equal to one. The exclusive control bit 105 remains in a low state when it transitions to the exclusive control bit 115. Likewise, the waiters control bit 107 maintains its low state when it transitions to the waiters control bit 117.
FIG. 2 illustrates a typical technique for managing multiple access requests in a multi-threaded environment using a lock 201 which transitions, in response to a contended request, to a lock 211 and a local wait block 221. The local wait block is added to a local wait block list. As discussed above, a contended case will result when an exclusive acquire thread 231 attempts to access a data object that has either previously been locked by an exclusive acquire thread or is currently locked and being accessed by one or more shared acquire threads. In a first example, the lock 201 identifies that a data object is exclusively locked by setting the exclusive acquire control bit 205 to a non-zero state. Alternatively, the lock 201 indicates that a data object is locked and being accessed by one or more shared acquire threads by indicating the number of shared acquire threads currently accessing the data object in the shared owners count control bit 203.
With continued reference to FIG. 2, in response to receiving an exclusive acquire thread 231 which results in a contended case, the lock 201 transitions to a lock 211 which contains a pointer 219 to a local wait block 221 and a waiters control bit 213. Additionally, for a contended case, a local wait block 221 including a saved share count 223 and an exclusive control bit 225 is generated for the thread that has been denied access to the data object. The pointer block 219 includes a reference to the local wait block 221. Additionally, in response to receiving an exclusive acquire thread 231 which results in a contended case, the waiters control bit 207 transitions to a high state to a waiters control bit 213 which indicates that there is currently at least one thread waiting to access the data object. The local wait block 221 includes a saved share count 223 and an exclusive control bit 225. The saved share count control bit 223 maintains the number of shared acquires that were currently accessing the data object prior to receipt of the exclusive acquire thread 231. Additionally, the exclusive control bit 225 maintains the status of the thread that caused contention. In this instance, because the thread causing contention, the exclusive acquire thread 231, is exclusive, the exclusive control bit 225 transitions to a high state.
A shared acquire thread 241 results in a contended case when the data object being managed by the lock 201 is currently locked by a previous exclusive acquire, indicated by the exclusive acquire control bit 205 being in a high state. In response to receiving a shared acquire thread 241, the lock 201 transitions to a lock 211 which includes a pointer 219 containing a reference to the local wait block 221 and increments the waiters control bit 213 by 1 to indicate the number of threads currently awaiting access to the data object, in this case one. Likewise, in response to receiving a shared acquire thread 241 which results in a contended case, the local waiters block 221 maintains a saved share count 223 which, in this example, will be zero (because the data object was locked by an exclusive acquire) and an exclusive acquire control bit 225 will transition to a low state, because the thread causing contention is a shared acquire thread 241.
In a typical case, after a contended case has caused one or more local wait blocks to be added to a local wait block list, releases are more complicated. Typically, the following rights are granted to a releasing thread (shared or exclusive) that is attempting to release an acquired data object that has met contention: (1) shared release threads are allowed to search the local wait block list until they identify a wait block with a non-zero saved share count (this will be a wait block marked exclusive). The thread is allowed to use an interlocked operation to decrement that value. If this thread transitioned the value to zero, then it attains the rights of an exclusive releasing thread; (2) exclusive releasing threads are allowed to search the local wait block list until they find a continuous chain of shared wait blocks or they find the last wait block in an exclusive waiting thread.
Additional acquires that meet contention are added to the head of the local wait block list. Once there is a contended case, all attempted acquires are queued in the local wait block.
In the current implementation of locks, as described above, ownership of the lock is passed from thread to thread. However, this results in a problem as releasing threads must traverse the local wait list to find the next thread to wake. As a result, the lock hold time on a data object is increased due to the increase in time to identify and wake the appropriate wait block and pass lock ownership to that thread. Thus, the wait block list is effectively protected by the lock itself.
Thus, there is a need for a system and method for efficiently managing thread requests for a data object in a multi-threaded environment that reduces wait time.